package com.umgsai.wx.backend.test;

public class TrappingRainWater {

    /**
     * 接雨水 https://leetcode-cn.com/problems/trapping-rain-water/submissions/
     *
     * @param args
     */
    public static void main(String[] args) {
//        int[] nums = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
//        int[] nums = new int[]{4, 2, 3};
//        int[] nums = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
//        int[] nums = new int[]{2, 4, 2, 3, 2, 1};
//        int[] nums = new int[]{9, 6, 8, 8, 5, 6, 3};
//        int[] nums = new int[]{2, 0, 2};
        int[] nums = new int[]{2, 6, 3, 8, 2, 7, 2, 5, 0};
        int trap = trap(nums);
        System.out.println(trap);
    }

    public static int trap(int[] nums) {
        int result = 0;
        if (nums == null || nums.length < 3) {
            return result;
        }
        int max = nums[0];
        int maxIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= max) {
                maxIndex = i;
                max = nums[i];
            }
        }
        int secondMax = -1;
        if (maxIndex == 0) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > secondMax && nums[i] < max) {
                    secondMax = nums[i];
                }
            }
            nums[0] = secondMax;
        }
        for (int index1 = 0; index1 < nums.length; index1++) {
            boolean existLower = false;
            int mostLow = -1;
            int mostHigh = 0;
            int index2 = 0;
            for (int j = index1 + 1; j < nums.length; j++) {
                index2 = j;
                if (nums[j] < nums[index1]) {
                    existLower = true;
                    if (mostLow == -1) {
                        mostLow = nums[j];
                    }
                    if (mostLow > nums[j]) {
                        mostLow = nums[j];
                    }
                }
                if (nums[j] > mostHigh) {
                    mostHigh = nums[j];
                }
                if (nums[j] >= nums[index1]) {
                    break;
                }
            }
            boolean breakAll = false;
            if (existLower && mostHigh > mostLow) {
                if (mostHigh >= nums[index1]) {
                    int calc = calc(nums, index1, index2);
                    result += calc;
                    index1 = index2 - 1;
                } else {
                    if (index2 == nums.length - 1) {
                        while (true) {
                            breakAll = true;
                            if (index2 == 0) {
                                break;
                            }
                            if (nums[index2] <= nums[index2 - 1]) {
                                index2--;
                            } else {
                                break;
                            }
                        }
                        int calc = calc(nums, index1, index2);
                        result += calc;
                    }
                }
            }
            if (breakAll) {
                break;
            }
        }
        return result;
    }

    public static int calc(int[] nums, int index1, int index2) {
        if (index1 >= index2) {
            return 0;
        }
        int head = nums[index1];
        int tail = nums[index2];
        int temp = Math.min(head, tail);
        int result = 0;
        for (int i = index1; i <= index2; i++) {
            int tempTrap = temp - nums[i];
            if (tempTrap < 0) {
                tempTrap = 0;
            }
            result += tempTrap;
        }
        return result;
    }
}
